package main

import "fmt"

type node struct {
	left, right, parent *node
	color               int
	Key                 string
	Value               interface{}
}

/*
将key按顺序排行，仅用于做程序上的比较
return [root][left][right]
*/
func (n *node) dumpKey() string {
	if n == nil {
		return ""
	}
	s := n.Key
	if getColor(n) == RED {
		s += "R"
	}
	if n.left != nil {
		s += n.left.dumpKey()
	}
	if n.right != nil {
		s += n.right.dumpKey()
	}

	return s
}

/*
构建 dot 语法
*/
func (n *node) dumpDot() string {
	s := ""
	if getColor(n) == RED {
		s = fmt.Sprintf(`"%v"[color=red];`, n.Key)
	} else {
		s = fmt.Sprintf(`"%v";`, n.Key)
	}

	if n.left != nil {
		s += fmt.Sprintf(`"%v"->"%v";`, n.Key, n.left.Key)
		s += n.left.dumpDot()
	}

	if n.right != nil {
		s += fmt.Sprintf(`"%v"->"%v";`, n.Key, n.right.Key)
		s += n.right.dumpDot()
	}

	return s
}

// Next returns the node's successor as an iterator.
func (n *node) Next() *node {
	return successor(n)
}

// successor returns the successor of the node
func successor(x *node) *node {
	if x.right != nil {
		return minimum(x.right)
	}
	y := x.parent
	for y != nil && x == y.right {
		x = y
		y = x.parent
	}
	return y
}

// getColor gets color of the node.
func getColor(n *node) int {
	if n == nil {
		return BLACK
	}
	return n.color
}

// minimum finds the minimum node of subtree n.
func minimum(n *node) *node {
	for n.left != nil {
		n = n.left
	}
	return n
}
